package sort

import (
//"fmt"
)

type Data interface {
	Less(i, j int) bool
	Swap(i, j int)
	Len() int
}

func FastSort(data Data, left, right int) {
	//fmt.Printf("left:%d right:%d \n", left, right)
	/*defer func() {
		if err := recover(); err != nil {
			fmt.Printf("recover error:")
		}
		//fmt.Printf("key:%d \n", key)
	}()*/

	if left < right {
		key := left
		i := left
		j := right
		for i < j {
			for i < j && data.Less(key, j) {
				j--
			}

			if i < j {
				data.Swap(i, j)
				key = j
				i++
			}

			for i < j && data.Less(i, key) {
				i++
			}

			if i < j {
				data.Swap(i, j)
				key = i
				j--
			}
		}

		if i > left {
			FastSort(data, left, i-1)
		}
		if right > i {
			FastSort(data, i+1, right)
		}
	}
}
